package com.learn.algorithm_1_march;

import java.util.HashMap;
import java.util.Map;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

/**
 * 两数之和，https://leetcode-cn.com/problems/two-sum/
 *
 * 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
 * 你可以假设【每种输入只会对应一个答案】。但是，你不能重复利用这个数组中同样的元素。
 */
public class TwoSum {

    /* 利用hashmap实现 */
    public int[] hashMap(int[] nums, int target) {
        int[] result = {-1, -1};
        //- 存储已遍历元素，key是元素（重复会被覆盖），value是下标
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            //- 匹配后，停止遍历
            if(map.containsKey(target - nums[i])){
                result[0] = map.get(target - nums[i]);
                result[1] = i;
                break;
            }
            // 验证匹配后再加入map，避免出现重复判断，比如 target 10 - 5 = 5
            map.put(nums[i], i);
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int target = 17;

        // 写法一
        int[] result = new TwoSum().hashMap(nums, target);
        System.out.println(IntStream.of(result).boxed().collect(Collectors.toList()));

        // 写法二
        // test(nums, target);
    }

    public static void test(int[] nums, int target){
        Map<Integer, Integer> map = new HashMap<>();
        IntStream.range(0, nums.length).forEach((i) -> {
            if (map.containsKey(target - nums[i])){
                System.out.println(String.format("匹配结果：[%d, %d]", i, map.get(target-nums[i])));
                return;
            }
            map.put(nums[i], i);
        });
    }
}
